package suanfa.string;

public class RK {


    public static void main(String[] args) {
        String str="aacdesadsdfer";

        String pattern="adsd";

        System.out.println("第一次出现的位置"+rabinKarps(str,pattern));
    }


    public static int rabinKarps(String str,String pattern){

        int m=str.length();

        int n=pattern.length();

        int patternCode=hash(pattern);

        int strCode=hash(str.substring(0,n));


        for (int i = 0; i < (m-n+1); i++) {
            if(strCode==patternCode && compareString(i,str,pattern)){
                return i;
            }

            if(i<(m-n)){
                strCode=nextHash(str,strCode,i,n);
            }


        }

        return -1;
    }

    private static int hash(String str){
        int hashCode=0;

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            int c_=c-'a';
            hashCode+=c_;
        }
        return hashCode;
    }

    private static int nextHash(String str,int hash,int index,int n){

        hash-=(str.charAt(index)-'a');
        hash+=(str.charAt(index+n)-'a');

        return hash;
    }

    private static boolean compareString(int i,String str,String pattern){
        String strSub=str.substring(i,i+pattern.length());

        return strSub.equals(pattern);
    }
}
